package com.sun;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 */
public class Test17电话号码的字母组合 {
    public static void main(String[] args){
        String digits = "234";
        List<String> strings = letterCombinations2(digits);
        strings.forEach(System.out::println);

    }

    /**
     *方法1：自己暴力循环,
     */
    public static List<String> letterCombinations1(String digits){
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()){
            return res;
        }
        HashMap<Character,List<String>> map = new HashMap<>(){{
            put('2',new ArrayList<>(){{add("a");add("b");add("c");}});
            put('3',new ArrayList<>(){{add("d");add("e");add("f");}});
            put('4',new ArrayList<>(){{add("g");add("h");add("i");}});
            put('5',new ArrayList<>(){{add("j");add("k");add("l");}});
            put('6',new ArrayList<>(){{add("m");add("n");add("o");}});
            put('7',new ArrayList<>(){{add("p");add("q");add("r");add("s");}});
            put('8',new ArrayList<>(){{add("t");add("u");add("v");}});
            put('9',new ArrayList<>(){{add("w");add("x");add("y");add("z");}});
        }};
        if (digits.length() == 1){
            return map.get(digits.charAt(0));
        }
        for (int i = 0; i < digits.length(); i++){
            List<String> strings1 = map.get(digits.charAt(i));
            for (int j = i+1; j < digits.length(); j++) {
                List<String> strings2 = map.get(digits.charAt(j));
                for (String s1 : strings1) {
                    for (String s2 : strings2) {
                        res.add(s1+s2);
                    }
                }

            }
        }
        return res;
    }

    /**
     * 方法2：力扣官方 回溯方法
     */
    public static List<String> letterCombinations2(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        callBack(combinations,digits,phoneMap,0, new StringBuilder());
        return combinations;
    }

    public static void callBack(List<String> combinations, String digits,Map<Character,String > phoneMap,
                                int index, StringBuilder tempString){

        if (index == digits.length()){
            combinations.add(tempString.toString());
        }else {
            char phone = digits.charAt(index);
            String phoneString = phoneMap.get(phone);
            int length = phoneString.length();
            for (int i = 0; i < length; i++) {
                tempString.append(phoneString.charAt(i));
                callBack(combinations, digits, phoneMap, index + 1, tempString);
                tempString.deleteCharAt(index);
            }
        }
    }


}
